package LinkedList;
//判断单链表是否回文
//思路：1、找到中间节点
//     2、将后半部分翻转
//     3、头尾同时开始遍历，判断是否回文，相遇了则说明是（偶数节点数
//        为特殊情况，另外考虑）
public class Solution7 {
    public boolean chkPalindrome(ListNode A) {
        ListNode cur = A;
        ListNode db = A;
        ListNode head = A;
        if(A == null || A.next == null) {
            return true;
        }
        while (db!=null&&db.next!=null) {
            cur = cur.next;
            db = db.next.next;
        }
        if(cur.next==null){
            if(head.val==cur.val){
                return true;
            }else {
                return false;
            }
        }
        ListNode pre = null;
        ListNode next = cur.next;
        while (next.next!=null){
            pre = cur;
            cur = next;
            next = next.next;
            cur.next=pre;
        }
        next.next = cur;
        cur = next;
        while(head!=cur){
            if(head.next != cur){
                if(head.val==cur.val){
                    head = head.next;
                    cur = cur.next;
                }else {
                    return false;
                }
            }else {
                if(head.val==cur.val){
                    return true;
                }else {
                    return false;
                }
            }
        }
        return true;


    }
}
